<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 统计和小于目标的下标对数目
        // 时间复杂度：O(n^2)
        // 空间复杂度：O(1)
        // 题目已经说过，假定只存在唯一的一个解
        var threeSumClosest = function(nums, target) {
            // 排序
            nums.sort((a, b) => a - b)
            let ans = 0; // 结果
            let minDiff = Infinity // target和三数和的最小差
            let n = nums.length
            for (let i = 0; i < nums.length - 2; i++) {
                let value = nums[i]

                /* 注意，下面的三个优化都是写在for循环里面的 */
                // 优化1，如果当前数和上一个相等，直接不遍历了
                if (i > 0 && value === nums[i - 1]) {
                    continue
                }

                // 优化2，如果前三个数相加大于target，则后续只会更大
                let s = value + nums[i + 1] + nums[i + 2]
                if (s > target) {
                    if (s - target < minDiff) {
                        ans = s
                    }
                    break
                }

                // 优化3，如果第一个数和最后两个数小于target，则第一个数和中间任意数相加都小于target
                s = value + nums[n - 1] + nums[n - 2]
                if (s < target) {
                    if (target - s < minDiff) {
                        minDiff = target - s
                        ans = s
                    }
                    continue
                }
                let j = i + 1;
                let k = n - 1
                while (j < k) {
                    s = value + nums[j] + nums[k]
                    if (s === target) {
                        return target
                    } else if (s < target) {
                        if (target - s < minDiff) {
                            minDiff = target - s
                            ans = s
                        }
                        j++
                    } else if (s > target) {
                        if (s - target < minDiff) {
                            minDiff = s - target
                            ans = s
                        }
                        k--
                    }
                }
            }
            return ans
        };
        console.log(threeSumClosest([0, 1, 2], 0));
        // console.log(threeSumClosest([-1,2,1,-4], 1));
    </script>
</body>
</html>